#include <vector>
using namespace std;
class Solution
{
public:
    int lenLongestFibSubseq(vector<int> &arr)
    {
        vector<vector<int>> dp(arr.size() - 1, vector<int>(arr.size()));
        int res = 0;
        // 确定最后两个数递推 dp[j][k]=dp[i][j]+1;
        for (int i = 0; i < arr.size() - 2; i++)
        {
            for (int k = i + 2; k < arr.size(); k++)
            {
                // 二分优化 找j
                int l = i + 1, r = k - 1;
                while (l < r)
                {
                    int mid_j = (l + r) >> 1;
                    if (arr[i] + arr[mid_j] < arr[k])
                        l = mid_j + 1;
                    else
                        r = mid_j;
                }
                if (arr[r] + arr[i] != arr[k])
                    continue;
                if (!dp[i][r])
                    dp[i][r] += 2;
                dp[r][k] = dp[i][r] + 1;
                res = max(res, dp[r][k]);
            }
        }
        return res;
    }
};